|
Quicksearch ist eine neue Variante des Algorithmus BoMo von Boyer
und Moore zur Mustersuche in Texten. Sie ist bei Texten in
natürlichen Sprachen, das heißt solchen mit relativ großen
Alphabeten, und bei der Suche nach relativ kurzen Mustern den bisher
bekannten BoMo-Varianten ebenbürtig, übertrifft sie aber bei
langen Mustern und kleinen Alphabeten, wie sie bei der Suche nach
Genetischem Code vorkommen, um einen Faktor von ca. 1.25 bei der
Musterlänge 10 und bis zu einem Faktor > 2 bei Mustern ab der
Größe 40.
QuickSearch is a new variant of BoMo, the Boyer-Moore algorithm for
pattern matching in strings. For strings with relatively large
alphabets such as natural-language texts and for short patterns, it
matches with presently known BoMo variants; for long patterns and
short alphabets as do occur in Genetic Code, it surpasses these
variants by a factor 1.25 at pattern length 10, and up to a factor
> 2 for patterns of length greater 40.
|